package com.hdu.other.dp.pakege01;

import java.io.*;

/**
 * <a href="https://www.luogu.com.cn/problem/P1048">01背包模板</a>
 */
public class Template {


    private static final int MAX_N = 101;

    private static final int[] VALUE = new int[MAX_N];
    private static final int[] COST = new int[MAX_N];

    private static int T;
    private static int M;

    public static void main(String[] args) throws IOException {

        BufferedReader reader = new BufferedReader(new java.io.InputStreamReader(System.in));
        PrintWriter writer = new PrintWriter(new OutputStreamWriter(System.out));
        StreamTokenizer st = new StreamTokenizer(reader);

        while (st.nextToken() != StreamTokenizer.TT_EOF) {
            T = (int) st.nval;
            st.nextToken();
            M = (int) st.nval;
            for (int i = 0; i < M; i++) {
                st.nextToken();
                COST[i] = (int) st.nval;
                st.nextToken();
                VALUE[i] = (int) st.nval;
            }
            writer.println(cal());
        }

        writer.flush();
        reader.close();
        writer.close();
    }

    private static int cal() {
        int[] dp = new int[T + 1];
        for (int i = 0; i < M; i++) {
            for (int j = T; j >= COST[i]; j--)
            {
                dp[j] = Math.max(dp[j], dp[j - COST[i]] + VALUE[i]);
            }
        }
        return dp[T];
    }
}
